package org.example.likou150.tree;

import java.util.Stack;

public class TreeIterator {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        TreeIterator treeIterator = new TreeIterator();
        System.out.println("------------前序递归遍历------------");
        treeIterator.preIterator(root); //124536
        System.out.println();
        System.out.println("------------前序栈遍历------------");
        treeIterator.preStackIterator(root);
        System.out.println();
        System.out.println("------------中序递归遍历------------");
        treeIterator.centerIterator(root); //425136
        System.out.println("------------中序栈遍历------------");
        treeIterator.centerStackIterator(root);
    }

    // 前序递归遍历——根、左、右
    public TreeNode preIterator(TreeNode root){
        if(root==null){
            return null;
        }
        System.out.print(root.val);
        preIterator(root.left);
        preIterator(root.right);
        return root;
    }

    // 前序栈遍历
    void preStackIterator(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            if(treeNode!=null){
                System.out.print(treeNode.val);
                stack.push(treeNode.right);
                stack.push(treeNode.left);
            }
        }
    }

    // 中序递归遍历——左、根、右
    public TreeNode centerIterator(TreeNode root){
        if(root==null){
            return null;
        }
        centerIterator(root.left);
        System.out.print(root.val);
        centerIterator(root.right);
        return root;
    }
    // 中序栈遍历
    public void centerStackIterator(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = root;
        while (currentNode!=null || !stack.isEmpty()){
            while (currentNode!=null){
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.val);
            currentNode = treeNode.right;
        }
    }

    // 后续遍历
    public TreeNode postIterator(TreeNode root){
        if(root==null){
            return null;
        }
        postIterator(root.left);
        postIterator(root.right);
        System.out.println(root.val);
        return root;
    }



    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
